import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 538. 把二叉搜索树转换为累加树
 */
public class Solution_538 {
    int sum = 0;

    /**
     * 反向中序遍历
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(N)
     */
    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }

    /**
     * 中序遍历 + 栈
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(N)
     */
    public TreeNode convertBST1(TreeNode root) {
        if (root == null) {
            return null;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        inorder(root, stack);
        TreeNode next = stack.pop();
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            cur.val += next.val;
            next = cur;
        }
        return root;
    }

    private void inorder(TreeNode node, Deque<TreeNode> stack) {
        if (node != null) {
            inorder(node.left, stack);
            stack.push(node);
            inorder(node.right, stack);
        }
    }
}
